Key agreement is a fundamental tool for secure communication. A key agreement scheme lets two nodes in a network agree on a shared key that is known only to them, thus allowing them to use that key for secure communication. In environments where bandwidth is at a premium, there is a significant advantage to non-interactive schemes, where two nodes can compute their shared key without any interaction. The classical Diffie-Hellman key-exchange protocol, which is described in W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, 22(6):644-654 (1976), is an example of such a non-interactive scheme. In the Diffie-Hellman key-exchange protocol, node A can compute a shared key with node B knowing only the public key of B and its own secret or private key. But each node in this protocol must still learn the public key of the other node, implying either direct communication between the nodes or some other form of coordination.
To minimize the required coordination between nodes, an identity-based key-exchange is used where the public key of a node is the name of that node. These schemes rely on a key distribution center (KDC), which is a central authority with a master secret key, to provide each node with a secret key that corresponds to the name of that node. An example of this scheme is described in R. Sakai, K. Ohgishi, and M. Kasahara, Cryptosystems Based on Pairings, Proceedings of SCIS 2000 (2000), where node A computes a shared key with node B knowing only the name of its own secret key.
Registering all nodes with just one central authority, however, is not always practical or possible. For example, in mobile ad-hoc networks (MANETs), frequent communications occur between nodes from different organizational units. In environments such as MANETs, a hierarchical system is preferred, where the central authority only needs to distribute keys to a small number of large organizations. Each of these large organizations can further distribute keys to smaller and smaller units until individual nodes obtain secret keys from their immediate unit. Such a hierarchical scheme would serve well also for tactical network applications where the organization of the network is already hierarchical in nature. Preferred schemes would be non-interactive, identity-based and hierarchical and would hold together with a strong security guarantee.
A previous attempt to provide a suitable scheme was proposed in Carlo Blundo, Alfredo De Santis, Amir Herzberg, Shay Kutten, Ugo Vaccaro, and Moti Yung, Perfectly Secure Key Distribution for Dynamic Conferences, Information and Computation, 146(1):1-23 (1998). According to the proposed scheme, each node has a secret polynomial that provides the role of a secret key. The shared key between two leaf nodes is computed by evaluating the polynomial of one node at a point that corresponds to the identity of the other. The main drawback of this proposed scheme is that security is ensured only as long as not too many nodes are compromised. Once the number of compromised nodes grows above some threshold, an attacker could learn keys of un-compromised nodes and perhaps the master secret key of the whole system. This threshold is essentially the degree of the polynomials that are used in that scheme. This vulnerability is particularly acute in MANETs, where the ad-hoc nature of the network makes it very hard to assure the integrity of nodes. In MANETs, therefore, a high enough threshold to ensure security in a realistic setting may not be possible.